package com.study;

/**
 * @program: leetcode
 * @author: jzhou
 * @date: 2022-11-13 11:02
 * @version: 1.0
 * @description: 排列硬币
 * 总共有 n 个硬币，将他们排成一个阶梯形状，第 k 行正好有 k 个硬币，给定一个n，找出形成完整阶梯的总行数
 **/
public class ArrangeCoin {
    public static void main(String[] args) {
        System.out.println(arrangeCoin(100));
        System.out.println(arrangeCoin2(100));
        System.out.println(arrangeCoin3(100));
    }


    // 迭代 一行一行排，排完一行就将这些硬币从总数中减去
    private static int arrangeCoin(int n) {
        for (int i = 1; i <= n; i++) {
            n = n - i;
            if(n <= i){
                return i;
            }
        }
        return 0;
    }

    // 二分查找  行数一定小于硬币总数    利用 n 行 共有  (n + 1 ) * n / 2 个
    // 取中间行数 计算硬币数 与 给定硬币数对比
    private static int arrangeCoin2(int n) {
        int low = 0, high = n;
        while (low <= high){
            int mid = (high - low)/2 + low;
            int total = (mid + 1) * mid / 2;
            if (total == n){
                return mid;
            }else if (total > n){
                high = mid - 1;
            }else {
                low = mid + 1;
            }
        }
        return high;
    }


    // 牛顿迭代
    private static int arrangeCoin3(int n) {
        if (n == 0)
            return 0;
        return  (int)sqrt(n,n);
    }

    private static double sqrt(int n, double x) {
        double res = ((2*n - x )/x + x)/2;
        if(res == x){
            return res;
        }

        return sqrt(n,res);
    }
}
